#include <bits/stdc++.h>

using namespace std;
class LockingTree
{
private:
    vector<int> parent_;
    vector<int> flag_;
    vector<vector<int>> child_;

public:
    LockingTree(vector<int> &parent)
        : parent_(parent)
    {
        flag_.resize(parent.size(), -1);
        child_.resize(parent.size());
        for (int i = 0; i < parent.size(); ++i)
        {
            if (parent[i] != -1)
            {
                child_[parent[i]].push_back(i);
            }
        }
    }

    bool lock(int num, int user)
    {
        if (flag_[num] == -1)
        {
            flag_[num] = user;
            return true;
        }
        return false;
    }

    bool unlock(int num, int user)
    {
        if (flag_[num] == user)
        {
            flag_[num] = -1;
            return true;
        }
        return false;
    }

    bool upgrade(int num, int user)
    {
        // 判断当前节点
        if (flag_[num] != -1)
        {
            return false;
        }
        // 判断祖先节点
        for (int i = parent_[num]; i != -1; i = parent_[i])
        {
            if (flag_[i] != -1)
            {

                return false;
            }
        }
        // 判断子孙节点
        if (!check(num))
        {

            return false;
        }
        flag_[num] = user;
        return true;
    }

    bool check(int num)
    {
        bool ret = flag_[num] != -1;
        flag_[num] = -1;
        for (int child : child_[num])
        {
            ret |= check(child);
        }
        return ret;
    }
};